<!doctype html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>



<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />












  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.0" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="算法," />








  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.1.0" />






<meta name="description" content="从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

例如abc的全排列：

abc
acb
bac
bca
cab
cba

共 3! = 3  2  1 = 6，六种。">
<meta property="og:type" content="article">
<meta property="og:title" content="算法拾遗之【全排列算法】">
<meta property="og:url" content="https://vector-ding.coding.me/algorithm/permutations/index.html">
<meta property="og:site_name" content="Vector's Notes">
<meta property="og:description" content="从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

例如abc的全排列：

abc
acb
bac
bca
cab
cba

共 3! = 3  2  1 = 6，六种。">
<meta property="og:updated_time" content="2017-03-12T09:58:46.426Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="算法拾遗之【全排列算法】">
<meta name="twitter:description" content="从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

例如abc的全排列：

abc
acb
bac
bca
cab
cba

共 3! = 3  2  1 = 6，六种。">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    sidebar: {"position":"left","display":"post"},
    fancybox: true,
    motion: true,
    duoshuo: {
      userId: '6378305291301160000',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://vector-ding.coding.me/algorithm/permutations/"/>





  <title> 算法拾遗之【全排列算法】 | Vector's Notes </title>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  










  
  
    
  

  <div class="container one-collumn sidebar-position-left page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-meta ">
  

  <div class="custom-logo-site-title">
    <a href="/"  class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <span class="site-title">Vector's Notes</span>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>
    
      <p class="site-subtitle"></p>
    
</div>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-algorithm">
          <a href="/categories/algorithm/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-superscript"></i> <br />
            
            Algorithm
          </a>
        </li>
      
        
        <li class="menu-item menu-item-java">
          <a href="/categories/java/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-coffee"></i> <br />
            
            Java
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
  <link itemprop="mainEntityOfPage" href="https://vector-ding.coding.me/algorithm/permutations/">

  <span style="display:none" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <meta itemprop="name" content="vector.ding">
    <meta itemprop="description" content="">
    <meta itemprop="image" content="/assets/img/vector.ding.jpg">
  </span>

  <span style="display:none" itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
    <meta itemprop="name" content="Vector's Notes">
    <span style="display:none" itemprop="logo" itemscope itemtype="http://schema.org/ImageObject">
      <img style="display:none;" itemprop="url image" alt="Vector's Notes" src="">
    </span>
  </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
            
            
              
                算法拾遗之【全排列算法】
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2017-03-12T16:29:03+08:00">
                2017-03-12
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/algorithm/permutations/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count ds-thread-count" data-thread-key="algorithm/permutations/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          

          
          

          

          

        </div>
      </header>
    


    <div class="post-body" itemprop="articleBody">

      
      

      
        <blockquote>
<p>从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。<br></p>
</blockquote>
<p>例如abc的全排列：</p>
<ol>
<li>abc</li>
<li>acb</li>
<li>bac</li>
<li>bca</li>
<li>cab</li>
<li>cba</li>
</ol>
<p>共 3! = 3 <em> 2 </em> 1 = 6，六种。</p>
<a id="more"></a>
<p>算法课上我们学到了将问题分解，而编程语言又允许我们使用递归这种符合数学推理的思维去解决问题。那么我们一起来看看n-1的全排列和n的全排列之间有没有规律可循，以bc和abc为例：</p>
<p>bc的全排列</p>
<ul>
<li>bc</li>
<li>cb</li>
</ul>
<p>abc的全排列</p>
<ul>
<li>abc</li>
<li>acb</li>
<li>bac</li>
<li>bca</li>
<li>cab</li>
<li>cba</li>
</ul>
<p>有以下规律:</p>
<ol>
<li>每个字母都会出现在第一位，并且出现的次数相等</li>
<li>针对首字母分组后，每一组都由以该首字母为开头和其余的n-1位的全排列组合的所有组合</li>
</ol>
<p>我们不难发现</p>
<p>abc的全排列是由以a开头与bc的全排列组合、以b开头和ac的全排列组合、以c为开头和ab的全排列组合，三个组合之和组成abc的全排列。<br>
那么进一步：n个字符的全排列分别是由n个字符中的每一个字符开头和剩余n-1字符的全排列的的组合之和。</p>
<p>下面我们使用Java写实现上面的逻辑：</p>
<p>有两个的关键点:</p>
<ol>
<li><p>n到n-1的规模缩小不是一次完成的，需要循环遍历每一个字母排除后来构造n-1的规模</p>
<p> 一般我们会采用重用一个数组空间，使用下标控制边界的方法递归，这样节省方法栈空间。这里用一个比较巧妙的方法实现：
 循环当前规模的数组，将要作为开头的字母与数组第一个字母交换，那么array[0]就是开头的字母，array[1…n]就是剩下的n-1的规模；但是要注意的是，我们破坏了原有的数组结构，因此必须在排完array[1…n]之后，重新恢复数组的结构，即重新交换回。（越解释越乱，可以直接看代码，代码更直观）</p>
</li>
<li><p>什么条件下算是排出一组</p>
<p> 我们使用下标控制问题规模，当规模缩小到一个数字的时候，就算是排出一组，并且我们移动了数组元素，此时的数组结构便是排出的一个组合，输出即可。</p>
</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">package</span> io.vector.study.algorithm.permutation;</div><div class="line"></div><div class="line"><span class="keyword">import</span> com.alibaba.fastjson.JSON;</div><div class="line"></div><div class="line"><span class="comment">/**</span></div><div class="line"> * Created by vector on 2017/3/6.</div><div class="line"> */</div><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Permutation</span> </span>&#123;</div><div class="line"></div><div class="line">    <span class="keyword">public</span> &lt;T extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; <span class="function"><span class="keyword">void</span> <span class="title">resolve</span><span class="params">(T[] array)</span> </span>&#123;</div><div class="line">        <span class="keyword">if</span> (array == <span class="keyword">null</span> || array.length == <span class="number">0</span>) &#123;</div><div class="line">            <span class="keyword">return</span> ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        doResolve(array, <span class="number">0</span>, array.length - <span class="number">1</span>);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">private</span> &lt;T extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; <span class="function"><span class="keyword">void</span> <span class="title">doResolve</span><span class="params">(T[] array, <span class="keyword">int</span> start, <span class="keyword">int</span> end)</span> </span>&#123;</div><div class="line"></div><div class="line">        <span class="keyword">if</span> (start == end) &#123;</div><div class="line">            System.out.println(JSON.toJSONString(array));</div><div class="line">            <span class="keyword">return</span> ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> index = start; index &lt;= end; ++index) &#123;</div><div class="line">            swap(array, index, start);</div><div class="line">            doResolve(array, start + <span class="number">1</span>, end);</div><div class="line">            swap(array, index, start);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">private</span> &lt;T extends Comparable&lt;? <span class="keyword">super</span> T&gt;&gt; <span class="function"><span class="keyword">void</span> <span class="title">swap</span><span class="params">(T[] array, <span class="keyword">int</span> index1, <span class="keyword">int</span> index2)</span> </span>&#123;</div><div class="line">        <span class="keyword">if</span> (index1 == index2) &#123;</div><div class="line">            <span class="keyword">return</span> ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        T temp = array[index1];</div><div class="line">        array[index1] = array[index2];</div><div class="line">        array[index2] = temp;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">&#125;</div></pre></td></tr></table></figure>
      
    </div>

    <div>
      
        

      
    </div>

    <div>
      
        

      
    </div>


    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/算法/" rel="tag"># 算法</a>
          
        </div>
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/java/synchorized/" rel="next" title="Java中synchronized用法">
                <i class="fa fa-chevron-left"></i> Java中synchronized用法
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div class="post-spread">
      
    </div>
  </div>

          
          </div>
          


          
  <div class="comments" id="comments">
    
      <div class="ds-thread" data-thread-key="algorithm/permutations/"
           data-title="算法拾遗之【全排列算法】" data-url="https://vector-ding.coding.me/algorithm/permutations/">
      </div>
    
  </div>


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      

      <section class="site-overview sidebar-panel sidebar-panel-active">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/assets/img/vector.ding.jpg"
               alt="vector.ding" />
          <p class="site-author-name" itemprop="name">vector.ding</p>
          <p class="site-description motion-element" itemprop="description">Elegant Coding</p>
        </div>
        <nav class="site-state motion-element">
        
          
            <div class="site-state-item site-state-posts">
              <a href="/archives">
                <span class="site-state-item-count">9</span>
                <span class="site-state-item-name">日志</span>
              </a>
            </div>
          

          
            <div class="site-state-item site-state-categories">
              <a href="/categories">
                <span class="site-state-item-count">9</span>
                <span class="site-state-item-name">分类</span>
              </a>
            </div>
          

          
            <div class="site-state-item site-state-tags">
              <a href="/tags">
                <span class="site-state-item-count">9</span>
                <span class="site-state-item-name">标签</span>
              </a>
            </div>
          

        </nav>

        

        <div class="links-of-author motion-element">
          
        </div>

        
        

        
        

        


      </section>

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy; 
  <span itemprop="copyrightYear">2017</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">vector.ding</span>
</div>


<div class="powered-by">
  由 <a class="theme-link" href="https://hexo.io">Hexo</a> 强力驱动
</div>

<div class="theme-info">
  主题 -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Pisces
  </a>
</div>


        

        
      </div>
    </footer>

    <div class="back-to-top">
      <i class="fa fa-arrow-up"></i>
    </div>
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  




  
  <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.0"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.0"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.0"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.0"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.0"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.0"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.0"></script>



  

  
    
  

  <script type="text/javascript">
    var duoshuoQuery = {short_name:"vector-ding"};
    (function() {
      var ds = document.createElement('script');
      ds.type = 'text/javascript';ds.async = true;
      ds.id = 'duoshuo-script';
      ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js';
      ds.charset = 'UTF-8';
      (document.getElementsByTagName('head')[0]
      || document.getElementsByTagName('body')[0]).appendChild(ds);
    })();
  </script>

  
    
    
    <script src="/lib/ua-parser-js/dist/ua-parser.min.js?v=0.7.9"></script>
    <script src="/js/src/hook-duoshuo.js"></script>
  












  
  

  

  

  

  

</body>
</html>
